{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #K Empty Slots"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #array #ordered-set #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #数组 #有序集合 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kEmptySlots"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #K 个关闭的灯泡"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><code>n</code>&nbsp;个灯泡排成一行，编号从 <code>1</code> 到<meta charset=\"UTF-8\" />&nbsp;<code>n</code>&nbsp;。最初，所有灯泡都关闭。每天&nbsp;<strong>只打开一个</strong>&nbsp;灯泡，直到<meta charset=\"UTF-8\" />&nbsp;<code>n</code>&nbsp;天后所有灯泡都打开。</p>\n",
    "\n",
    "<p>给你一个长度为<meta charset=\"UTF-8\" />&nbsp;<code>n</code>&nbsp;的灯泡数组 <code>blubs</code> ，其中 <code>bulbs[i] = x</code> 意味着在第 <code>(i+1)</code> 天，我们会把在位置 <code>x</code> 的灯泡打开，其中 <code>i</code> <strong>从 0 开始</strong>，<code>x</code> <strong>从 1 开始</strong>。</p>\n",
    "\n",
    "<p>给你一个整数<meta charset=\"UTF-8\" />&nbsp;<code>k</code>&nbsp;，请返回<em>恰好有两个打开的灯泡，且它们中间 <strong>正好</strong> 有<meta charset=\"UTF-8\" />&nbsp;<code>k</code>&nbsp;个&nbsp;<strong>全部关闭的</strong> 灯泡的 <strong>最小的天数</strong> </em>。<em>如果不存在这种情况，返回 <code>-1</code> 。</em></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>示例 1：</b></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>\n",
    "bulbs = [1,3,2]，k = 1\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "第一天 bulbs[0] = 1，打开第一个灯泡 [1,0,0]\n",
    "第二天 bulbs[1] = 3，打开第三个灯泡 [1,0,1]\n",
    "第三天 bulbs[2] = 2，打开第二个灯泡 [1,1,1]\n",
    "返回2，因为在第二天，两个打开的灯泡之间恰好有一个关闭的灯泡。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>bulbs = [1,2,3]，k = 1\n",
    "<strong>输出：</strong>-1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><b>提示：</b></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == bulbs.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= bulbs[i] &lt;= n</code></li>\n",
    "\t<li><code>bulbs</code> 是一个由从 <code>1</code> 到 <code>n</code> 的数字构成的排列</li>\n",
    "\t<li><code>0 &lt;= k &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [k-empty-slots](https://leetcode.cn/problems/k-empty-slots/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [k-empty-slots](https://leetcode.cn/problems/k-empty-slots/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2]\\n1', '[1,2,3]\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        added = []\n",
    "        for i, bulb in enumerate(bulbs):\n",
    "            if len(added) > 0:\n",
    "                ip = bisect.bisect_left(added, bulb)\n",
    "                if ip == 0:\n",
    "                    if added[ip] - bulb == k+1:\n",
    "                        return i+1\n",
    "                elif ip == len(added):\n",
    "                    if bulb - added[ip-1] == k+1:\n",
    "                        return i+1\n",
    "                else: \n",
    "                    if (bulb - added[ip-1] == k+1) or (added[ip] - bulb == k+1):\n",
    "                        return i+1\n",
    "            bisect.insort_left(added, bulb)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n=len(bulbs)\n",
    "        arr=[]\n",
    "        ans=-1\n",
    "        for i,v in enumerate(bulbs):\n",
    "            bisect.insort_left(arr,v)\n",
    "            j=arr.index(v)\n",
    "            if j-1>=0:\n",
    "                l=arr[j-1]\n",
    "                if v-l-1==k:\n",
    "                    return i+1\n",
    "\n",
    "            if j+1<len(arr):\n",
    "                r=arr[j+1]\n",
    "                if r-v-1==k:\n",
    "                    return i+1\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def kEmptySlots(self, flowers, k):\n",
    "        days = [0] * len(flowers)\n",
    "        for day, position in enumerate(flowers, 1):\n",
    "            days[position - 1] = day\n",
    "\n",
    "        ans = float('inf')\n",
    "        left, right = 0, k+1\n",
    "        while right < len(days):\n",
    "            for i in range(left + 1, right):\n",
    "                if days[i] < days[left] or days[i] < days[right]:\n",
    "                    left, right = i, i+k+1\n",
    "                    break\n",
    "            else:\n",
    "                ans = min(ans, max(days[left], days[right]))\n",
    "                left, right = right, right+k+1\n",
    "\n",
    "        return ans if ans < float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def kEmptySlots(self, bulbs, k):\n",
    "        days = [0] * len(bulbs)\n",
    "        for day, position in enumerate(bulbs, 1):\n",
    "            days[position - 1] = day\n",
    "\n",
    "        ans = float('inf')\n",
    "        left, right = 0, k+1\n",
    "        while right < len(days):\n",
    "            for i in range(left + 1, right):\n",
    "                if days[i] < days[left] or days[i] < days[right]:\n",
    "                    left, right = i, i+k+1\n",
    "                    break\n",
    "            else:\n",
    "                ans = min(ans, max(days[left], days[right]))\n",
    "                left, right = right, right+k+1\n",
    "\n",
    "        return ans if ans < float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        # bulbs to days \n",
    "        # [1, 3, 2] -> [0, 2, 1]\n",
    "        # [1, 2, 3] -> [0, 1, 2]\n",
    "        n = len(bulbs)\n",
    "        position_days = [0 for _ in range(len(bulbs))]\n",
    "        for i in range(len(bulbs)):\n",
    "            position_days[bulbs[i] - 1 ] = i \n",
    "\n",
    "\n",
    "        # sliding window \n",
    "        l = 0\n",
    "        r = 0 + k + 1\n",
    "        ans = float('inf')\n",
    "        while r < n:\n",
    "            # check each l, r is the smallest \n",
    "            for i in range(l+1, r):\n",
    "                if position_days[i] < position_days[l] or position_days[i] < position_days[r]:\n",
    "                    # not working, position i is smaller\n",
    "                    l = i\n",
    "                    r = l + k + 1\n",
    "                    break\n",
    "            else:\n",
    "                # no break means [l, r] meets the condition , l, r is the smallest\n",
    "                ans = min(ans, max(position_days[l], position_days[r]) + 1 )\n",
    "\n",
    "                # no smaller within [l, r] move the window \n",
    "                l = r\n",
    "                r = l + k + 1\n",
    "\n",
    "\n",
    "        return ans if ans != float('inf') else -1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def kEmptySlots(self, bulbs, k):\n",
    "        days = [0] * len(bulbs)\n",
    "        for day, position in enumerate(bulbs):\n",
    "            days[position - 1] = day + 1\n",
    "\n",
    "        ans = float('inf')\n",
    "        left, right = 0, k+1\n",
    "        while right < len(days):\n",
    "            flag = 0\n",
    "            for i in range(left + 1, right):\n",
    "                if days[i] < days[left] or days[i] < days[right]:\n",
    "                    left, right = i, i+k+1\n",
    "                    flag = 1\n",
    "                    break\n",
    "\n",
    "            if not flag:\n",
    "                ans = min(ans, max(days[left], days[right]))\n",
    "                left, right = right, right+k+1\n",
    "\n",
    "        return ans if ans < float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryIndexedTree:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.c = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, x, delta):\n",
    "        while x <= self.n:\n",
    "            self.c[x] += delta\n",
    "            x += x & -x\n",
    "    \n",
    "    def query(self, x):\n",
    "        s = 0\n",
    "        while x:\n",
    "            s += self.c[x]\n",
    "            x -= x & -x\n",
    "        return s\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n = len(bulbs)\n",
    "        tree = BinaryIndexedTree(n)\n",
    "        for i, x in enumerate(bulbs, 1):\n",
    "            tree.update(x, 1)\n",
    "            y = x - k - 1\n",
    "            if y > 0 and tree.query(y) - tree.query(y - 1) == 1 and tree.query(x - 1) - tree.query(y) == 0:\n",
    "                return i\n",
    "            y = x + k + 1\n",
    "            if y <= n and tree.query(y) - tree.query(y - 1) == 1 and tree.query(x + k) - tree.query(x) == 0:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n = len(bulbs)\n",
    "        f = [False] * (n+1)\n",
    "        \n",
    "\n",
    "        for i, b in enumerate(bulbs):\n",
    "            f[b] = True\n",
    "            \n",
    "            if b > k+1 and f[b-k-1]:\n",
    "                invalid = False\n",
    "                for j in range(b-1, b-k-1, -1):\n",
    "                    if f[j]:\n",
    "                        invalid = True\n",
    "                        break\n",
    "\n",
    "                if not invalid:\n",
    "                    return i+1\n",
    "            \n",
    "            if b < n-k and f[b+k+1]:\n",
    "                invalid = False\n",
    "                for j in range(b+1, b+k+1):\n",
    "                    if f[j]:\n",
    "                        invalid = True\n",
    "                        break\n",
    "\n",
    "                if not invalid:\n",
    "                    return i+1\n",
    "            \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect \n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n = len(bulbs)\n",
    "        sl = [bulbs[0]]\n",
    "        for i in range(1,n):\n",
    "            idx = bisect.bisect_left(sl, bulbs[i])\n",
    "            if idx == 0:\n",
    "                if sl[idx] - bulbs[i] == k + 1:\n",
    "                    return i +1\n",
    "                sl.insert(idx, bulbs[i]) \n",
    "            elif idx == len(sl):\n",
    "                if bulbs[i] - sl[idx-1] == k+1:\n",
    "                    return i +1\n",
    "                sl.append(bulbs[i]) \n",
    "            else:\n",
    "                if bulbs[i] - sl[idx-1] == k+1 or sl[idx] - bulbs[i] == k+1:\n",
    "                    return i +1 \n",
    "                sl.insert(idx, bulbs[i])\n",
    "        return -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        # bulbs to days \n",
    "        # [1, 3, 2] -> [0, 2, 1]\n",
    "        # [1, 2, 3] -> [0, 1, 2]\n",
    "        n = len(bulbs)\n",
    "        position_days = [0 for _ in range(len(bulbs))]\n",
    "        for i in range(len(bulbs)):\n",
    "            position_days[bulbs[i] - 1 ] = i \n",
    "\n",
    "\n",
    "        # sliding window \n",
    "        l = 0\n",
    "        r = 0 + k + 1\n",
    "        ans = float('inf')\n",
    "        while r < n:\n",
    "            # check each l, r is the smallest \n",
    "            for i in range(l+1, r):\n",
    "                if position_days[i] < position_days[l] or position_days[i] < position_days[r]:\n",
    "                    # not working, position i is smaller\n",
    "                    l = i\n",
    "                    r = l + k + 1\n",
    "                    break\n",
    "            else:\n",
    "                # no break means [l, r] meets the condition , l, r is the smallest\n",
    "                ans = min(ans, max(position_days[l], position_days[r]) + 1 )\n",
    "\n",
    "                # no smaller within [l, r] move the window \n",
    "                l = r\n",
    "                r = l + k + 1\n",
    "\n",
    "\n",
    "        return ans if ans != float('inf') else -1\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        # bulbs to days \n",
    "        # [1, 3, 2] -> [0, 2, 1]\n",
    "        # [1, 2, 3] -> [0, 1, 2]\n",
    "        n = len(bulbs)\n",
    "        position_days = [0 for _ in range(len(bulbs))]\n",
    "        for i in range(len(bulbs)):\n",
    "            position_days[bulbs[i] - 1 ] = i \n",
    "\n",
    "\n",
    "        # sliding window \n",
    "        l = 0\n",
    "        r = 0 + k + 1\n",
    "        ans = float('inf')\n",
    "        while r < n:\n",
    "            # check each l, r is the smallest \n",
    "            for i in range(l+1, r):\n",
    "                if position_days[i] < position_days[l] or position_days[i] < position_days[r]:\n",
    "                    # not working, position i is smaller\n",
    "                    l = i\n",
    "                    r = l + k + 1\n",
    "                    break\n",
    "            else:\n",
    "                # no break means [l, r] meets the condition , l, r is the smallest\n",
    "                ans = min(ans, max(position_days[l], position_days[r]) + 1 )\n",
    "\n",
    "                # no smaller within [l, r] move the window \n",
    "                l = r\n",
    "                r = l + k + 1\n",
    "\n",
    "\n",
    "        return ans if ans != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n=len(bulbs)\n",
    "        arr=[]\n",
    "        ans=-1\n",
    "        for i,v in enumerate(bulbs):\n",
    "            bisect.insort_left(arr,v)\n",
    "            j=arr.index(v)\n",
    "            if j-1>=0:\n",
    "                l=arr[j-1]\n",
    "                if v-l-1==k:\n",
    "                    return i+1\n",
    "            if j+1<len(arr):\n",
    "                r=arr[j+1]\n",
    "                if r-v-1==k:\n",
    "                    return i+1\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def kEmptySlots(self, bulbs, k):\n",
    "        days = [0] * len(bulbs)\n",
    "        for day, position in enumerate(bulbs, 1):\n",
    "            days[position - 1] = day\n",
    "\n",
    "        ans = float('inf')\n",
    "        left, right = 0, k+1\n",
    "        while right < len(days):\n",
    "            for i in range(left + 1, right):\n",
    "                if days[i] < days[left] or days[i] < days[right]:\n",
    "                    left, right = i, i+k+1\n",
    "                    break\n",
    "            else:\n",
    "                ans = min(ans, max(days[left], days[right]))\n",
    "                left, right = right, right+k+1\n",
    "\n",
    "        return ans if ans < float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def kEmptySlots(self, bulbs, k):\n",
    "        days = [0] * len(bulbs)\n",
    "        for day, position in enumerate(bulbs):\n",
    "            days[position - 1] = day + 1\n",
    "\n",
    "        ans = float('inf')\n",
    "        left, right = 0, k+1\n",
    "        while right < len(days):\n",
    "            for i in range(left + 1, right):\n",
    "                if days[i] < days[left] or days[i] < days[right]:\n",
    "                    left, right = i, i+k+1\n",
    "                    break\n",
    "            else:\n",
    "                ans = min(ans, max(days[left], days[right]))\n",
    "                left, right = right, right+k+1\n",
    "\n",
    "        return ans if ans < float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n = len(bulbs)\n",
    "        days = [0] * n \n",
    "        for i in range(n):\n",
    "            days[bulbs[i] - 1] = i  \n",
    "        l = 0\n",
    "        r = l + k + 1 \n",
    "        res = float('inf')\n",
    "        while r < n:\n",
    "            for i in range(l + 1, r):\n",
    "                if days[i] < days[l] or days[i] < days[r]:\n",
    "                    l = i\n",
    "                    r = i + k + 1\n",
    "                    break\n",
    "            else:\n",
    "                res = min(res, max(days[l], days[r]))\n",
    "                l = r  \n",
    "                r = l + k + 1 \n",
    "        return res + 1 if res != float('inf') else - 1\n",
    "\n",
    "\n",
    "        n = len(bulbs)\n",
    "        pos = [0] * n \n",
    "        for i in range(n):\n",
    "            pos[bulbs[i] - 1] = i\n",
    "        l = 0\n",
    "        r = l + k + 1 \n",
    "        res = float('inf')\n",
    "        while r < n:\n",
    "            for i in range(l + 1, r):\n",
    "                if pos[i] < pos[l] or pos[i] < pos[r]:\n",
    "                    l = i \n",
    "                    r = i + k + 1 \n",
    "                    break \n",
    "            else:\n",
    "                res = min(res, max(pos[l], pos[r]))\n",
    "                l = r \n",
    "                r = l + k + 1 \n",
    "        return res + 1 if res != float('inf') else - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        mins = deque([])\n",
    "        days = [0] * len(bulbs)\n",
    "        for day, position in enumerate(bulbs, 1):\n",
    "            days[position - 1] = day\n",
    "        for i in range(min(k+1,len(days))):\n",
    "            while len(mins)!=0 and days[mins[len(mins)-1]]>days[i]:\n",
    "                mins.pop()\n",
    "            mins.append(i)\n",
    "        ans = -1\n",
    "        for i in range(k+1,len(days)):\n",
    "            prev = mins[0]\n",
    "            if prev==i-k-1:\n",
    "                mins.popleft()\n",
    "            while len(mins)!=0 and days[mins[len(mins)-1]]>days[i]:\n",
    "                mins.pop()\n",
    "            if len(mins)==0 and prev==i-k-1:\n",
    "                if ans==-1 or max(days[prev],days[i])<ans:\n",
    "                    ans = max(days[prev],days[i])\n",
    "            mins.append(i)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n = len(bulbs)\n",
    "        pos = [0] * n \n",
    "        for i in range(n):\n",
    "            pos[bulbs[i] - 1] = i\n",
    "        l = 0\n",
    "        r = l + k + 1 \n",
    "        res = float('inf')\n",
    "        while r < n:\n",
    "            for i in range(l + 1, r):\n",
    "                if pos[i] < pos[l] or pos[i] < pos[r]:\n",
    "                    l = i \n",
    "                    r = i + k + 1 \n",
    "                    break \n",
    "            else:\n",
    "                res = min(res, max(pos[l], pos[r]))\n",
    "                l = r \n",
    "                r = l + k + 1 \n",
    "        return res + 1 if res != float('inf') else - 1\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        pre = SortedList()\n",
    "        for i, bulb in enumerate(bulbs):\n",
    "            j = pre.bisect_right(bulb)\n",
    "            for x in [j - 1, j]:\n",
    "                if 0 <= x < len(pre) and abs(pre[x] - bulb) - 1 == k:\n",
    "                    return i + 1\n",
    "            pre.add(bulb)\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n = len(bulbs)\n",
    "        l, r = 1, n\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if self.check(mid, bulbs, k):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        if not self.check(r, bulbs, k):\n",
    "            return -1\n",
    "        return r\n",
    "\n",
    "    def check(self, day, bulbs, k):\n",
    "        window = SortedList()\n",
    "        for i in range(day):\n",
    "            window.add(bulbs[i])\n",
    "            idx = window.index(bulbs[i])\n",
    "            if (0 <= idx - 1 < len(window) and window[idx] - window[idx-1] - 1 == k) or \\\n",
    "               (0 <= idx + 1 < len(window) and window[idx+1] - window[idx] - 1 == k):\n",
    "               return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    # Bisect. Time O(nlog^2n) Space O(n)\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n = len(bulbs)\n",
    "        l, r = 1, n\n",
    "        while l < r:\n",
    "            mid = (l + r) // 2\n",
    "            if self.check(mid, bulbs, k):\n",
    "                r = mid\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        if not self.check(r, bulbs, k):\n",
    "            return -1\n",
    "        return r\n",
    "\n",
    "    def check(self, day, bulbs, k):\n",
    "        window = SortedList()\n",
    "        for i in range(day):\n",
    "            window.add(bulbs[i])\n",
    "            idx = window.index(bulbs[i])\n",
    "            if (0 <= idx - 1 < len(window) and window[idx] - window[idx-1] - 1 == k) or \\\n",
    "               (0 <= idx + 1 < len(window) and window[idx+1] - window[idx] - 1 == k):\n",
    "               return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    # Bisect. Time O(nlog^2n) Space O(n)\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n = len(bulbs)\n",
    "        window = SortedList()\n",
    "        for i in range(n):\n",
    "            window.add(bulbs[i])\n",
    "            idx = window.index(bulbs[i])\n",
    "            if (0 <= idx - 1 < len(window) and window[idx] - window[idx-1] - 1 == k) or \\\n",
    "               (0 <= idx + 1 < len(window) and window[idx+1] - window[idx] - 1 == k):\n",
    "               return i + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    # Bisect. Time O(nlogn) Space O(n)\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n = len(bulbs)\n",
    "        window = SortedList()\n",
    "        for i in range(n):\n",
    "            window.add(bulbs[i])\n",
    "            idx = window.index(bulbs[i])\n",
    "            if (0 <= idx - 1 < len(window) and window[idx] - window[idx-1] - 1 == k) or \\\n",
    "               (0 <= idx + 1 < len(window) and window[idx+1] - window[idx] - 1 == k):\n",
    "               return i + 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        from sortedcontainers import SortedList\n",
    "        sl = SortedList()\n",
    "        for i,x in enumerate(bulbs):\n",
    "            j = sl.bisect_left(x)\n",
    "            for idx in (j - 1,j):\n",
    "                if 0 <= idx < len(sl) and abs(sl[idx] - x) - 1 == k:\n",
    "                    return i + 1\n",
    "            sl.add(x)\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n=len(bulbs)\n",
    "        s=sorted(zip(bulbs,range(n)))\n",
    "        #print(s)\n",
    "        light=[]\n",
    "        for i,b in enumerate(bulbs):\n",
    "            j=bisect_left(light,b)\n",
    "            for x in [j-1,j]:\n",
    "                if 0 <= x < len(light) and abs(light[x] - b) - 1 == k:\n",
    "                    return i + 1\n",
    "            insort_left(light,b)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n=len(bulbs)\n",
    "        s=sorted(zip(bulbs,range(n)))\n",
    "        #print(s)\n",
    "        light=[]\n",
    "        for i,b in enumerate(bulbs):\n",
    "            j=bisect_left(light,b)\n",
    "            for x in [j-1,j]:\n",
    "                if 0 <= x < len(light) and abs(light[x] - b) - 1 == k:\n",
    "                    return i + 1\n",
    "            insort_left(light,b)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        # d代表位置i的灯开启的天数为d[i]\n",
    "        # 位置从[0,n-1]，天数[0,n-1]\n",
    "        if k + 2 > len(bulbs):\n",
    "            return -1\n",
    "        d = [0] * len(bulbs)\n",
    "        for i in range(len(bulbs)):\n",
    "            x = bulbs[i]\n",
    "            d[x-1] = i\n",
    "\n",
    "        res = float(\"inf\")\n",
    "        if k == 0:\n",
    "            for i in range(len(bulbs)-1):\n",
    "                max_day = max(d[i], d[i+1])\n",
    "                res = min(res, max_day)\n",
    "            if res == float(\"inf\"):\n",
    "                return -1\n",
    "            else:\n",
    "                return res+1\n",
    "        # 构造长度为k的滑动窗口的小顶堆\n",
    "        left, right = d[0], d[k+1]\n",
    "        small = [(d[i], i) for i in range(1, k+1)]\n",
    "        heapq.heapify(small)\n",
    "        max_day = max(left, right)\n",
    "        if max_day < small[0][0]:\n",
    "            res = min(res, max_day)\n",
    "        \n",
    "        # 我们希望找到连续k个位置的灯是灭的 且两端是亮的\n",
    "        # 两端的天数< 中间k个灯的天数的最小值\n",
    "        # d[i], d[i+k+1] < 滑动窗口最小值\n",
    "        for i in range(1, len(bulbs)-k-1):\n",
    "            heapq.heappush(small, (d[i+k], i+k))\n",
    "            while small[0][1] <= i:\n",
    "                heapq.heappop(small)\n",
    "            left, right = d[i], d[i+k+1]\n",
    "            max_day = max(left, right)\n",
    "            if max_day < small[0][0]:\n",
    "                res = min(res, max_day)\n",
    "        if res == float(\"inf\"):\n",
    "            return -1\n",
    "        else:\n",
    "            return res + 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n = len(bulbs)\n",
    "        possible_start = set()\n",
    "        light = set()\n",
    "\n",
    "        for i in range(1, n-k):\n",
    "            possible_start.add(i)\n",
    "        \n",
    "        for day, idx in enumerate(bulbs):\n",
    "            for i in range(max(idx-k, 1), min(idx, n-k)):\n",
    "                possible_start.discard(i)\n",
    "\n",
    "            if len(possible_start) == 0:\n",
    "                return -1\n",
    "            \n",
    "            if idx - k - 1 in light and idx - k - 1 in possible_start:\n",
    "                return day + 1\n",
    "            \n",
    "            if idx + k + 1 in light and idx in possible_start:\n",
    "                return day + 1\n",
    "            \n",
    "            light.add(idx)\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        turned_on = set()\n",
    "\n",
    "        def check_between(b1, b2):\n",
    "            for i in range(b1 + 1, b2):\n",
    "                if i in turned_on:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        for day, bulb in enumerate(bulbs, 1):\n",
    "            for diff in [-k-1, k+1]:\n",
    "                neighbor = bulb + diff\n",
    "                if 1 <= neighbor <= len(bulbs) and neighbor in turned_on:\n",
    "                    if check_between(min(bulb, neighbor), max(bulb, neighbor)):\n",
    "                        return day\n",
    "            turned_on.add(bulb)\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n = len(bulbs)\n",
    "        possible_start = set()\n",
    "        light = set()\n",
    "\n",
    "        for i in range(1, n-k):\n",
    "            possible_start.add(i)\n",
    "        \n",
    "        for day, idx in enumerate(bulbs):\n",
    "            for i in range(max(idx-k, 1), min(idx, n-k)):\n",
    "                possible_start.discard(i)\n",
    "\n",
    "            if len(possible_start) == 0:\n",
    "                return -1\n",
    "            \n",
    "            if idx - k - 1 in light and idx - k - 1 in possible_start:\n",
    "                return day + 1\n",
    "            \n",
    "            if idx + k + 1 in light and idx in possible_start:\n",
    "                return day + 1\n",
    "            \n",
    "            light.add(idx)\n",
    "        \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        n = len(bulbs)\n",
    "        if (k + 2) > n:\n",
    "            return -1\n",
    "        # bulbs.reverse()\n",
    "        # d = [0] * (n + 2)\n",
    "        # ans = -1\n",
    "        # for i, pos in enumerate(bulbs):\n",
    "        #     length = d[pos - 1] + d[pos + 1] + 1\n",
    "        #     # print((i, length))\n",
    "        #     left = pos - d[pos - 1]\n",
    "        #     right = pos + d[pos + 1]\n",
    "        #     if length == k and left != 1 and right != n:\n",
    "        #         # print(pos)\n",
    "        #         ans = (n - i - 1)\n",
    "            \n",
    "        #     d[pos] = d[left] = d[right] = length\n",
    "        # return ans\n",
    "        t = [0] * n\n",
    "        for i, b in enumerate(bulbs):\n",
    "            t[b-1] = (i + 1)\n",
    "        bulbs = t\n",
    "        # print(bulbs)\n",
    "        if k == 0:\n",
    "            return min([max(bulbs[i], bulbs[i+1]) for i in range(n-1)])\n",
    "        heap = []\n",
    "        for i in range(1, k + 1):\n",
    "            heapq.heappush(heap, (bulbs[i], i))\n",
    "        left = 0\n",
    "        right = k + 1\n",
    "        ans = n + 1\n",
    "        while right < n:\n",
    "            lateday = max(bulbs[left], bulbs[right])\n",
    "            while heap[0][1] <= left:\n",
    "                heapq.heappop(heap)\n",
    "            if heap[0][0] > lateday:\n",
    "                ans = min(lateday, ans)\n",
    "            # else: \n",
    "            heapq.heappush(heap, (bulbs[right], right))\n",
    "            left += 1\n",
    "            right += 1\n",
    "        if ans == (n + 1):\n",
    "            return -1\n",
    "        else:\n",
    "            return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        active = SortedSet()\n",
    "        cnt = 0\n",
    "\n",
    "        for i, x in enumerate(bulbs):\n",
    "\n",
    "            active.add(x)\n",
    "\n",
    "            cnt += 1\n",
    "\n",
    "            pos = active.bisect_left(x)\n",
    "            # 不是最后一个\n",
    "            if pos != cnt - 1:\n",
    "\n",
    "                x_next = active[pos + 1]\n",
    "\n",
    "                if x_next - x == k + 1:\n",
    "                    return i + 1\n",
    "            if pos != 0:\n",
    "                x_pre = active[pos - 1]\n",
    "                if x - x_pre == k + 1:\n",
    "                    return i + 1\n",
    "        return -1\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        active = SortedSet()\n",
    "        cnt = 0\n",
    "        for i, x in enumerate(bulbs):\n",
    "            active.add(x)\n",
    "            cnt += 1\n",
    "            pos = active.bisect_left(x)\n",
    "            if pos != cnt - 1:\n",
    "                x_next = active[pos + 1]\n",
    "                if x_next - x == k + 1:\n",
    "                    return i + 1\n",
    "\n",
    "            if pos != 0:\n",
    "                x_pre = active[pos - 1]\n",
    "                if x - x_pre == k + 1:\n",
    "                    return i + 1\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "\n",
    "\n",
    "        active = SortedSet()\n",
    "        cnt = 0\n",
    "\n",
    "        for i, x in enumerate(bulbs):\n",
    "\n",
    "            active.add(x)\n",
    "\n",
    "            cnt += 1\n",
    "\n",
    "            pos = active.bisect_left(x)\n",
    "            # 不是最后一个\n",
    "            if pos != cnt - 1:\n",
    "\n",
    "                x_next = active[pos + 1]\n",
    "\n",
    "                if x_next - x == k + 1:\n",
    "                    return i + 1\n",
    "            if pos != 0:\n",
    "                x_pre = active[pos - 1]\n",
    "                if x - x_pre == k + 1:\n",
    "                    return i + 1\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedSet\n",
    "\n",
    "class Solution:\n",
    "    def kEmptySlots(self, bulbs: List[int], k: int) -> int:\n",
    "        active = SortedSet()\n",
    "        cnt = 0\n",
    "        for i, x in enumerate(bulbs):\n",
    "            active.add(x)\n",
    "            cnt += 1\n",
    "            pos = active.bisect_left(x)\n",
    "            if pos != cnt - 1:\n",
    "                x_next = active[pos + 1]\n",
    "                if x_next - x == k + 1:\n",
    "                    return i + 1\n",
    "\n",
    "            if pos != 0:\n",
    "                x_pre = active[pos - 1]\n",
    "                if x - x_pre == k + 1:\n",
    "                    return i + 1\n",
    "        return -1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
